#include <bits/stdc++.h>

using namespace std;

class SegmentTree {
public:
    SegmentTree(vector<int> &nums) {
        n = nums.size();
        tree = vector<int>(n * 4, 0);
        buildTree(nums, 0, n - 1, 1);
    }

    void update(int i, int val) {
        updateTree(0, n - 1, i, val, 1);
    }

    int sumRange(int i, int j) {
        return queryTree(0, n - 1, i, j, 1);
    }

private:
    vector<int> tree;
    int n;

    void buildTree(vector<int> &nums, int l, int r, int idx) {
        if (l == r) {
            tree[idx] = nums[l];
            return;
        }
        int mid = l + (r - l) / 2;
        buildTree(nums, l, mid, idx * 2);
        buildTree(nums, mid + 1, r, idx * 2 + 1);
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }

    void updateTree(int l, int r, int i, int val, int idx) {
        if (l == r) {
            tree[idx] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if (i <= mid) {
            updateTree(l, mid, i, val, idx * 2);
        } else {
            updateTree(mid + 1, r, i, val, idx * 2 + 1);
        }
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }

    int queryTree(int l, int r, int i, int j, int idx) {
        if (j < l || i > r) {
            return 0;
        }
        if (l >= i && r <= j) {
            return tree[idx];
        }
        int mid = l + (r - l) / 2;
        return queryTree(l, mid, i, j, idx * 2) + queryTree(mid + 1, r, i, j, idx * 2 + 1);
    }
};

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 11};
    SegmentTree st(nums);
    cout << st.sumRange(0, 2) << endl; // expected output: 9
    cout << st.sumRange(0, 3) << endl; // expected output: 16
    st.update(3, 8);
    cout << st.sumRange(0, 2) << endl; // expected output: 9
    cout << st.sumRange(0, 3) << endl; // expected output: 17
    return 0;
}
/**
在该实现中，SegmentTree 类代表线段树，包括一个 vector<int> 类型的 tree，它存放了线段树的所有节点值。构造函数 SegmentTree(vector<int>& nums) 负责构建线段树。update(int i, int val) 函数通过递归修改线段树的指定节点，实现快速区间更新。sumRange(int i, int j) 函数通过递归查询线段树的指定区间节点的值，实现快速区间求和。

在 buildTree() 函数中，递归实现二分法构建线段树。在 updateTree() 函数中，递归实现二分法修改线段树的节点。在 queryTree() 函数中，递归实现二分法查询线段树的节点，并计算区间和。
 */